/**
 * Created with IntelliJ IDEA
 * Description:
 * User: SEKI TOMOKI
 * Date: 2023-09-29
 * Time: 12:02
 */
import java.util.ArrayList;
import java.util.List;

import java.util.Arrays;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> answer = new ArrayList<>();

        // int[] counts = new int[nums.length];
        // for(int i = 0; i < nums.length; i++) {
        //     counts[nums[i] - 1]++;
        // }

        // for(int i = 0; i < counts.length; i++) {
        //     if(counts[i] == 0) {
        //         answer.add(i + 1);
        //     }
        // }

        //不使用额外空间的做法
        for(int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if(nums[index] > 0) {
                nums[index] = - nums[index];
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                answer.add(i + 1);
            }
        }
        return answer;
    }
}
